home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / pov / gen / animdat / btree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-22  |  9.7 KB  |  365 lines
  1. /*--------------------------------------------------------------*/
  2. /*            ANIMDAT 1.1                */
  3. /*        copyright 1992 - TODD SANKEY            */
  4. /*                                */
  5. /*  The author hereby grants permission for the use and sharing    */
  6. /* of both source code end executable versions of this software    */
  7. /* at no charge. This software is not for sale and no other    */
  8. /* shall charge for it without the expressed consent of the    */
  9. /* author.                            */
  10. /*                                */
  11. /*  The source code can be freely modified, but it must retain    */
  12. /* the original copyright notice, and the author must be    */
  13. /* notified of these changes if the altered code is to be    */
  14. /* distributed.                            */
  15. /*--------------------------------------------------------------*/
  16.  
  17.  
  18. /*--------------------------------------------------------------*/
  19. /* btree.c    Routines for creating and evaluating a binary    */
  20. /*        tree representation of a mathematical        */
  21. /*        expression. Requires the scanner and error    */
  22. /*        modules.                    */
  23. /*--------------------------------------------------------------*/
  24.  
  25.  
  26. #include <string.h>
  27. #include <math.h>
  28. #include <stdlib.h>
  29. #include <stdio.h>
  30. #include "common.h"
  31.  
  32.  
  33. /* Local procedures */
  34. static btree_node_ptr    alloc_node();
  35. static btree_node_ptr    simple_expression();
  36. static btree_node_ptr    term();
  37. static btree_node_ptr    factor();
  38. static btree_node_ptr    unop();
  39.  
  40.  
  41. /*--------------------------------------------------------------*/
  42. /* btree_node_ptr    Allocate a node for a binary tree.    */
  43. /*--------------------------------------------------------------*/
  44. static btree_node_ptr alloc_node()
  45. {
  46.  btree_node_ptr    np;
  47.  
  48.  np=(btree_node_ptr)malloc(sizeof(btree_node));
  49.  if (np==NULL)
  50.     error(FAILED_MALLOC,NULL);
  51.  
  52.  np->left = NULL;
  53.  np->right = NULL;
  54.  return (np);
  55. }
  56.  
  57.  
  58.  
  59. /*----------------------------------------------------------------------*/
  60. /* expression        Process an expression consisting of a simple    */
  61. /*            expression optionally followed by a relational    */
  62. /*            operator and a simple expression.        */
  63. /*----------------------------------------------------------------------*/
  64. btree_node_ptr expression()
  65. {
  66.  btree_node_ptr    ltree,btree;
  67.  
  68.  /* Parse first simple expression */
  69.  btree=simple_expression();
  70.  
  71.  /* Now if there is a relational operator, remember it and process the
  72.     second simple expression */
  73.  if ( (token == EQUAL) || (token == LT) || (token == GT) ||
  74.       (token == NE) || (token == LE) || (token == GE) ) {
  75.  
  76.     ltree = btree;
  77.     btree = alloc_node();
  78.     btree->node_type = BINARYOP;
  79.     btree->node_data.operator = token;
  80.  
  81.     get_token();        /* required by scanner module after using
  82.                    operator token             */
  83.  
  84.     btree->left = ltree;
  85.     btree->right = simple_expression();
  86.     }
  87.  
  88.  return (btree);
  89. }
  90.  
  91.  
  92.  
  93. /*----------------------------------------------------------------------*/
  94. /* simple_expression    Process a simple expression consisting of terms    */
  95. /*            separated by +,-, or OR operators. There may be    */
  96. /*            a unary + or - in front of the first term.    */
  97. /*----------------------------------------------------------------------*/
  98. btree_node_ptr simple_expression()
  99. {
  100.  btree_node_ptr    btree,ltree;
  101.  
  102.  btree = term();
  103.  
  104.  /* Loop to process all terms separated by operators */
  105.  while ( (token == PLUS) || (token == MINUS) || (token == OR) ) {
  106.     ltree = btree;
  107.     btree = alloc_node();
  108.     btree->node_type = BINARYOP;
  109.     btree->node_data.operator = token;
  110.     get_token();
  111.     btree->left = ltree;
  112.     btree->right = term();
  113.     }
  114.  
  115.  return (btree);
  116. }
  117.  
  118.  
  119. /*----------------------------------------------------------------------*/
  120. /* term            Process a term consisting of factors separated    */
  121. /*            by *, /, %, or AND operators.            */
  122. /*----------------------------------------------------------------------*/
  123. btree_node_ptr term()
  124. {
  125.  btree_node_ptr btree,ltree;
  126.  
  127.  btree = factor();
  128.  
  129.  /* Loop to process all factors */
  130.  while ( (token == STAR) || (token == SLASH) ||
  131.      (token == AND) || (token == PERCENT)) {
  132.     ltree = btree;
  133.     btree = alloc_node();
  134.     btree->node_type = BINARYOP;
  135.     btree->node_data.operator = token;
  136.     get_token();
  137.     btree->left = ltree;
  138.     btree->right = factor();
  139.     }
  140.  
  141.  return (btree);
  142. }
  143.  
  144.  
  145. /*----------------------------------------------------------------------*/
  146. /* factor        Process a factor which consists of unops    */
  147. /*            separated by ^ (exponentiation) symbols.    */
  148. /*----------------------------------------------------------------------*/
  149. btree_node_ptr factor()
  150. {
  151.  btree_node_ptr btree,ltree;
  152.  
  153.  btree = unop();
  154.  
  155.  while ( (token == CARET) ) {
  156.     ltree = btree;
  157.     btree = alloc_node();
  158.     btree->node_type = BINARYOP;
  159.     btree->node_data.operator = token;
  160.     get_token();
  161.     btree->left = ltree;
  162.     btree->right = unop();
  163.     }
  164.  
  165.  return (btree);
  166. }
  167.  
  168.  
  169. /*----------------------------------------------------------------------*/
  170. /* unop            Process all unary operator symbols consisting    */
  171. /*            of +, -, SIN, COS, TAN, EXP, LOG, RND        */
  172. /*            followed by an                    */
  173. /*            identifier, a number, or a parenthesized    */
  174. /*            subexpression.                    */
  175. /*----------------------------------------------------------------------*/
  176. btree_node_ptr unop()
  177. {
  178.  btree_node_ptr btree,ltree;
  179.  
  180.  switch (token) {
  181.  
  182.     case IDENTIFIER :
  183.     case NUMSCENE :
  184.         btree = alloc_node();
  185.         btree->node_type = NAMEDVAR;
  186.         btree->node_data.name = (char *)malloc(strlen(word_string)+1);
  187.         strcpy(btree->node_data.name,word_string);
  188.         btree->left = NULL;
  189.         btree->right = NULL;
  190.         get_token();
  191.         break;
  192.  
  193.     case NUMBER :
  194.         btree = alloc_node();
  195.         btree->node_type = NUMBERVAL;
  196.         btree->node_data.value = literal_value;
  197.         btree->left = NULL;
  198.         btree->right = NULL;
  199.         get_token();
  200.         break;
  201.  
  202.     case PLUS :
  203.     case MINUS :
  204.     case SIN :
  205.     case COS :
  206.     case TAN :
  207.     case EXP :
  208.     case LOG :
  209.     case RND :
  210.     case ASIN:
  211.     case ACOS:
  212.     case ATAN:
  213.         btree = alloc_node();
  214.         btree->node_type = UNARYOP;
  215.         btree->node_data.operator = token;
  216.         get_token();
  217.         btree->right = NULL;
  218.         btree->left = unop();
  219.         break;
  220.  
  221.     case LPAREN :
  222.         get_token();
  223.         btree = expression();
  224.         if ( token == RPAREN)
  225.             get_token();
  226.         else
  227.             error(MISSING_RPAREN,cur_line);
  228.         break;
  229.  
  230.     default :
  231.         error(INVALID_EXPRESSION,cur_line);
  232.         break;
  233.     }
  234.  
  235.  return (btree);
  236. }
  237.  
  238.  
  239. /*--------------------------------------------------------------*/
  240. /* display_btree    Display a binary tree in RPN form.    */
  241. /*--------------------------------------------------------------*/
  242. void display_btree(btree_node_ptr btree)
  243. {
  244.  if (btree != NULL) {
  245.     display_btree(btree->left);
  246.     display_btree(btree->right);
  247.     switch (btree->node_type) {
  248.         case BINARYOP :
  249.         case UNARYOP :
  250.             printf(" %s",token_names[btree->node_data.operator]);
  251.             break;
  252.         case NUMBERVAL :
  253.             printf(" %lf",btree->node_data.value);
  254.             break;
  255.         case NAMEDVAR :
  256.             printf(" %s",btree->node_data.name);
  257.             break;
  258.         default :
  259.             error(FUNCTION_NOT_SUPPORTED,NULL);
  260.         }
  261.     }
  262. }
  263.  
  264.  
  265.  
  266.  
  267. /*--------------------------------------------------------------*/
  268. /* eval_binary        Evaluate the left and right subtrees    */
  269. /*            of a BINARYOP, apply the operator to     */
  270. /*            the results.                */
  271. /*--------------------------------------------------------------*/
  272. double eval_binary(btree_node_ptr btree)
  273. {
  274.  double left,right;
  275.  
  276.  left = eval_btree(btree->left);
  277.  right = eval_btree(btree->right);
  278.  
  279.  switch (btree->node_data.operator) {
  280.     case PLUS :    return (left + right);
  281.     case MINUS :    return (left - right);
  282.     case STAR :    return (left * right);
  283.     case SLASH :    return (left / right);
  284.     case PERCENT :    return fmod(left,right);
  285.     case CARET :    return ( exp(right * log(left)) );
  286.     case LT :    return ( (double)(left < right) );
  287.     case GT :    return ( (double)(left > right) );
  288.     case LE :    return ( (double)(left <= right) );
  289.     case GE :    return ( (double)(left >= right) );
  290.     case EQUAL :    return ( (double)(left == right) );
  291.     case NE :    return ( (double)(left != right) );
  292.     default :    error(FUNCTION_NOT_SUPPORTED,token_names[btree->node_data.operator]);
  293.     }
  294.  return (0.0);
  295. }
  296.  
  297.  
  298. /*--------------------------------------------------------------*/
  299. /* eval_unary        Evaluate the left subtree of a UNARYOP    */
  300. /*            node and apply the operator to the    */
  301. /*            result.                    */
  302. /*--------------------------------------------------------------*/
  303. double eval_unary(btree_node_ptr btree)
  304. {
  305.  double left;
  306.  
  307.  left = eval_btree(btree->left);
  308.  
  309.  switch (btree->node_data.operator) {
  310.     case PLUS :    return (left);
  311.     case MINUS :    return ( (-1.0)*left);
  312.     case SIN :    return (sin(left));
  313.     case COS :    return (cos(left));
  314.     case TAN :    return (tan(left));
  315.     case EXP :    return (exp(left));
  316.     case LOG :    return (log(left));
  317.     case RND :    srand((int)left); return ( (double)(rand())/(double)(RAND_MAX) );
  318.     case ASIN :    return (asin(left));
  319.     case ACOS :    return (acos(left));
  320.     case ATAN :    return (atan(left));
  321.     default :    error(FUNCTION_NOT_SUPPORTED,token_names[btree->node_data.operator]);
  322.     }
  323.  return (0.0);
  324. }
  325.  
  326.  
  327.  
  328. /*--------------------------------------------------------------*/
  329. /* eval_btree        Evaluate a binary tree.            */
  330. /*--------------------------------------------------------------*/
  331. double eval_btree(btree_node_ptr btree)
  332. {
  333.  double left,right;
  334.  
  335.  switch (btree->node_type) {
  336.     case NUMBERVAL: return (btree->node_data.value);
  337.  
  338.     case NAMEDVAR: return (eval_symbol(btree->node_data.name));
  339.  
  340.     case BINARYOP: return (eval_binary(btree));
  341.  
  342.     case UNARYOP: return (eval_unary(btree));
  343.  
  344.     default: error(SYNTAX_ERROR,NULL);
  345.     }
  346.  
  347.  return (0.0);
  348. }
  349.  
  350.  
  351.  
  352.  
  353. /*--------------------------------------------------------------*/
  354. /* traverse_btree    Recursively traverse a btree and call    */
  355. /*            the function once for each node.    */
  356. /*--------------------------------------------------------------*/
  357. void traverse_btree(btree_node_ptr btree, void (*f)(btree_node_ptr btree))
  358. {
  359.  if (btree != NULL) {
  360.     traverse_btree(btree->left,f);
  361.     traverse_btree(btree->right,f);
  362.     (*f)(btree);
  363.     }
  364. }
  365.